package com.yoshino.leetcode.improve40.twentyfirst;

/**
 * 思路：
 *  前缀树 + 遍历
 *  将字典值存入树中
 *  判断 方法：
 *  1.修改过，后续不能在改
 *  2.未修改过，对于当前结点可以遍历除自身对应的值外的其余非空值
 *  3.若在word末尾且 isEnd 且 修改过 返回true
 */
class MagicDictionary {

    class MatchNode {
        boolean isEnd;
        MatchNode[] next;
        public MatchNode() {
            next = new MatchNode[26];
        }
    }
    MatchNode root;
    /** Initialize your data structure here. */
    public MagicDictionary() {
        root = new MatchNode();
    }
    
    public void buildDict(String[] dictionary) {
        for (String s : dictionary) {
            MatchNode cur = root;
            for (char c : s.toCharArray()) {
                int ind = c - 'a';
                if (cur.next[ind] == null) {
                    cur.next[ind] = new MatchNode();
                }
                cur = cur.next[ind];
            }
            cur.isEnd = true;
        }
    }
    
    public boolean search(String searchWord) {
        return dfs(0, root, false, searchWord);
    }

    private boolean dfs(int ind, MatchNode cur, boolean isModify, String word) {
        if (ind == word.length()) {
            return isModify && cur.isEnd;
        }
        int i = word.charAt(ind) - 'a';
        if (cur.next[i] != null) {
            // 相等,继续遍历
            // 要是 下值为 false 仍然有机会 符合题意，如 未修改过
            if (dfs(ind + 1, cur.next[i], isModify, word)) {
                return true;
            }
        }
        if (!isModify) {
            for (int j = 0; j < 26; j++) {
                // 不能从自身即null向下探索
                if (cur.next[j] == null || j == i) {
                    continue;
                }
                if (dfs(ind + 1, cur.next[j], true, word)) {
                    // 已找到满足的
                    return true;
                }
            }
        }
        return false;
    }
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dictionary);
 * boolean param_2 = obj.search(searchWord);
 */